00100			     COMPUTER VISION
00200				   by
00300	             Thomas O. Binford, Stanford University    and
00400	             Jay M. Tenenbaum,  Stanford Research Institute
00500	
00600	
00700				Introduction.
00800	
00900	Computer perception is studied for its obvious practical applications
01000	and for the insights it provides into complex system organization and
01100	the nature of human  and  artificial  intelligence.  In  constructing
01200	machines that see, we seek answers to a broad range of questions: How
01300	should the system be partitioned functionally? What control structure
01400	is    needed?    What   are   inherent   computational   limits,   in
01500	interconnections for  parallel  machines;  in  computation  time  for
01600	serial machines?   Many of the problems encountered are widespread in
01700	intelligence: How is knowledge represented? How is it  integrated  in
01800	the system? How does it guide in drawing conclusions from image data?
01900	How does knowledge interact with conclusions drawn  from  the  image?
02000	Given  a  system,  what  can  it  see?   What is necessary for visual
02100	learning? What are given systems capable of  learning?  Many  results
02200	cannot be taken literally as models for biological systems because of
02300	differences in hardware and gaps in our  knowledge,  but  fundamental
02400	limitations  are  shared,  and  many  examples  are  applicable.  The
02500	research may occasionally borrow from biology,  but  we  cannot  copy
02600	nature,  since  the  details  are  not  known  and  the  hardware  is
02700	different.
02800	
02900	Issues that arise in mechanizing perception also arise in many  other
03000	areas  of artificial intelligence and computer science. Visualization
03100	is an important part of problem-solving and mathematics.  Graphs  and
03200	visual  displays  are  an  vital to communication.  Representation of
03300	knowledge and its use in goal-directed ways are universal problems in
03400	intelligence.
03500	
03600	Representations of shape are important in augmenting productivity and
03700	man-machine communication.   The use of computer graphics and  design
03800	automation  is  already  common in industry.  The information already
03900	available from these design processes can be used by computers to aid
04000	in  controlling  parts  and  material  flow,  in  designing transport
04100	systems,  in  extending  modularity  and  commonality  of  parts  and
04200	procedures,and   in   monitoring  and  scheduling  production.  These
04300	abilities,  which  require  some  of  the  most  sophisticated   A.I.
04400	techniques, will have a profound effect on near term productivity.
04500	
04600	Industry   uses   hundreds   of   industrial  robots,  some  computer
04700	controlled. Touch and simple vision can incrementally  improve  these
04800	robots  which  now  have  no sensing and thus no contingency actions.
04900	Sensor equipped robots coupled to  mini-computers  will  be  able  to
05000	sense  color and strong brightness contrasts, recognize known objects
05100	from two dimensional outlines (e.g., the top view of a  flat  object)
05200	or  three  dimensionally,  by  determining depth.  With these skills,
05300	they will be able to  align  mating  parts  in  assembly  operations,
05400	increase reliability by self-calibration, detect flaws and disasters,
05500	and permit large tolerances in parts transfer, even permitting  parts
05600	to be taken from a bin.
05700	
05800	
05900	We are interested in visual systems for function of an organism  such
06000	as  a  robot  that  must manipulate or avoid objects rather than just
06100	classifying   them.     Manipulation    requires    three-dimensional
06200	interpretations  and spatial relations of objects. Certain techniques
06300	have evolved for simpler problems; e.g.  template matching or  vector
06400	space  classification  for character recognition. It seems attractive
06500	to simply save images or feature vectors, then match against a  scene
06600	or  part  of  a  scene.  But  objects occlude one another, parts have
06700	joints  which  move  separately,  there  are  many  viewpoints,  many
06800	possible  objects,  and  many combinations of objects. Object classes
06900	are often defined by function, not shape (eg. coffee  cups).  Complex
07000	deductions  are  necessary to obtain spatial relations from an image.
07100	Finally, we must frequently deal with new  objects.  Direct  template
07200	matching techniques are impractical for these requirements, except in
07300	very carefully controlled applications.
     

00100		ELEMENTS OF A VISUAL SYSTEM
00200	
00300	The  computer  eye is some form of tv camera with color filters and a
00400	turret or zoom  lens  for  closeup  views.    The  computer  controls
00500	filters,  lens  and  other  parameters to optimize the image for each
00600	task [Tenenbaum].  Sensor systems have inadequate dynamic  range  but
00700	system  design studies suggest better compromises [Binford].   Humans
00800	use depth information  obtained  from  stereo  and  motion  parallax.
00900	Several  depth  sensors based on triangulation have been built [Agin,
01000	Shirai, Munson]. Range information with color should greatly simplify
01100	interpretation of scenes.
01200	
01300	The  image  is  read  into  memory  as  an array of brightness values
01400	(typically 300x300) with 4-8 bits for each sample for each color. The
01500	process  of  interpreting  this  mass  of  numbers  into  a  symbolic
01600	description can  be  thought  of  as  subdivided  into  segmentation,
01700	representation, and interpretation.
01800	
01900	The  process of segmentation of a scene partitions it into meaningful
02000	entities which  may  be  recognizable.    Segmentation  in  character
02100	recognition  is simple since printed characters are clearly separated
02200	and labelled by black on white. It is harder to segment objects in  a
02300	real  scene  (even  simple  scenes)  because  there are many possible
02400	properties for segmentation: uniformity of brightness, color, texture
02500	(itself  a  complex descriptor), regularity of boundaries, contiguity
02600	of depth (given stereo or other  depth  measurements).   Segmentation
02700	may  also  depend  on  depth  cues  from  interpretation  of  texture
02800	gradients and occlusion.
02900	
03000	In what form do we represent objects internally in the computer?  The
03100	simplest  form is a pictorial template, an array of brightness values
03200	to be matched directly against fragments of  scenes  by  correlation.
03300	Given  the  inadequacies  of  this  representation,  we must describe
03400	partitioned regions symbolically in terms of extracted features  like
03500	color,  size,  texture, and shape.  All these properties are inferred
03600	by complex processes from the image.  Simple descriptors for shape or
03700	texture may be used in simple tasks and limited context.  Shape might
03800	be described by the ratio of the squared perimeter to the area  of  a
03900	region.  More sophisticated shape representations, needed for a wider
04000	range of tasks, are described later.
04100	
04200	Interpretation is often expressed as  computing  a  distance  measure
04300	between  an  object and a stored model.  For simple cases that can be
04400	useful.   When objects are occluded, there must be a  partial  match.
04500	When  objects  are  not  identical, judgments of similarity depend on
04600	representation of shape and representation of the task, in  order  to
04700	define  important  differences.  The most useful approach is to build
04800	up  symbolic  descriptions  and   make   symbolic   descriptions   of
04900	differences.   Sometimes,  there  are few enough models that matching
05000	with each model is possible. More generally, interpretation must make
05100	use of a large visual memory.
05200	
05300	Because  of the evident interconnection of these three processes, one
05400	cannot proceed sequentially through segmentation, representation  and
05500	interpretation   and   expect   to   obtain   a  globally  consistent
05600	interpretation for all objects  in  a  scene.  Segmentation  must  be
05700	guided   by   interpretation   to   choose   among  many  alternative
05800	segmentations and interpretations to achieve globally consistent  and
05900	reasonable interpretations.
     

00100			BLOCKS WORLD
00200	
00300	To avoid some of these difficulties, research concentrated  initially
00400	on  scenes  of  blocks.  Roberts' important work opened the field [].
00500	Objects were represented as built up  of  three  primitive  parts,  a
00600	block,  a  wedge, and a hexagonal prism. The program assumed it would
00700	first obtain perfect line drawings. Interpretation  meant  finding  a
00800	three-dimensional model which after translation, rotation and scaling
00900	could be projected to match part of the image.  The recognized  piece
01000	was  then  cut  away  and  the remainder considered.  Primitives were
01100	represented by their vertices in three  dimensions.    To  decide  on
01200	likely  image  points  which  belonged  to a single body, the program
01300	attempted  to  identify  unobscured  polygons,  then  match  sets  of
01400	vertices  to topologically similar model vertices. Line drawings were
01500	formed by a sequence of local operations.  Candidate edge points were
01600	considered  by  thresholding the gradient of intensity. Isolated edge
01700	points were discarded.  Connected line  fragments  were  concatenated
01800	into  lines  which  were  segmented  at corners by a sequential least
01900	squares line fit.  Merging of colinear lines bridged some gaps.
02000	
02100	That system organization has proven inadequate. It is not  enough  to
02200	use  models and template matching. Producing perfect line drawings is
02300	not practical:  some  lines  are  missed;  shadows,  reflections  and
02400	surface  markings  cause  extra  lines;  errors made at one stage are
02500	compounded by later stages.  These deficiencies motivated  subsequent
02600	research.
02700	
02800	Guzman  []  found  it possible to segment complex scenes into objects
02900	without template matching, by observing that some vertices give local
03000	evidence  that adjacent regions belong to the same body. In figure 2,
03100	vertices A,B, and C give evidence that adjacent regions belong to the
03200	same  body.    But  vertex  D  gives  wrong  evidence.  To avoid such
03300	coincidences, the program required confirmation.      Regions  linked
03400	twice  were  joined  into clusters; regions linked twice to a cluster
03500	were also joined.  Regions linked only to a single cluster were  also
03600	joined  to  that  cluster. Eventually, the program evolved to include
03700	inhibitions against certain links by requiring similar conditions  at
03800	both  ends  of  a  line.   Other  links  were introduced without much
03900	motivation.   This program was an important advance.    Bodies  could
04000	be  segmented  without  recognition and without explicit models.  The
04100	program did surprisingly well, but had problems with holes and  other
04200	non-convexities,  and  with  accidental  alignment.    It depended on
04300	being told the background.  It was also unsatisfactory, since it  was
04400	not  an understanding but recipes for segmentation.  These techniques
04500	did not extend far. Falk [] realized that missing edges cause regions
04600	to  be  non-planar, and that by joining lines together into bodies by
04700	techniques similar to those of Guzman, some errors could  be  avoided
04800	which allowed these techniques to deal with imperfect line drawings.
04900	
05000	Huffman  []  and  Clowes [] made theoretical analyses of objects with
05100	only  trihedral  vertices  (three  planes  at  each  vertex).      By
05200	classifying  edges  as  convex,  concave  and  obscuring,  they could
05300	require consistent labels for a drawing, and reject some drawings  as
05400	impossible  objects  under their conditions.   Waltz [] expanded that
05500	labelling of lines to include cracks  and  whether  adjacent  regions
05600	were  shadowed  or illuminated. Each vertex had many interpretations.
05700	It would seem that such large  numbers  of  possible  interpretations
05800	would   be   unmanageable.    instead,  the  increased  precision  of
05900	descriptions allows rapid discarding of wrong  interpretations.   Not
06000	only  are solutions possible, they are quickly obtained. Instead of a
06100	complete tree  search,  it  was  adequate  to  consider  vertices  in
06200	sequence, eliminating inconsistent interpretations as each new vertex
06300	was added.  This produced all possible interpretations  of  a  scene.
06400	However,   some   evaluations  were  possible  to  choose  reasonable
06500	interpretations, in cases with ambiguous interpretations.
06600	
06700	
06800	
06900	
07000	
07100	The best performance in segmenting image data is given by the  Shirai
07200	[]  and  the  Binford-Horn [] line finders.  Shirai's system performs
07300	much better.   However, it requires large  contrast  with  background
07400	(white  on black), and finds only features and objects for which cues
07500	are available from context.   The Binford-Horn system is able to find
07600	most  lines  in  a  scene  of  white  blocks on a white background in
07700	arbitrary lighting.  It misses a few lines which are found later, and
07800	garbles  some  vertices.    The  two  are complementary and should be
07900	combined.
08000	
08100	The two programs are based on different principles.  Shirai's program
08200	began  with  only  outer  boundaries,  and  tried to guess as much as
08300	possible at each stage.    At vertices,  the  extension  of  boundary
08400	lines  was  tested.  Completions for unterminated lines were searched
08500	for.    Additional lines were tested for at vertices, including  some
08600	parallel  to lines at adjacent vertices.  The use of context involved
08700	not changing thresholds, but using special-purpose operators:  verify
08800	a line at known position and angle; find a line through a vertex. The
08900	Binford-Horn system was intended to provide the  base  for  a  system
09000	such  as Shirai's by providing a partial line drawing without special
09100	background.  It used a local directional edge operator and an optimal
09200	curve  sequential  decision process to extend curves and test at each
09300	extension, whether to keep, terminate, or extend further.
09400	
09500	It is interesting  to  compare  these  systems  with  the  biological
09600	system.   Directional  edge  operators  are  scanned  over  the image
09700	[Binford, Hueckel]; these compare with the edge detector cells []  in
09800	higher  animals.    In  practice,  large gradients at reflections and
09900	curved surfaces cause masses of spurious edge fragments.  These  were
10000	eliminated  by  subtracting  the  local  average  at each point, thus
10100	subtracting out smooth gradients [Binford].  This process is familiar
10200	as lateral inhibition in the retina of animals.
10300	
10400	
10500	
     

00100			REAL WORLD VISION
00200	
00300	
00400	
00500	The  blocks  world  illustrates  many  basic   aspects   of   machine
00600	perception,   but   many   other  critical  problems  encountered  in
00700	perceiving real world scenes do not  arise.   Important  problems  in
00800	segmentation   were   avoided  by  using  uniformly  painted  blocks.
00900	Segmentation  of  boundaries  was  specialized  to  straight   lines.
01000	Region-growing and edge-finding techniques require generalizations to
01100	regions of uniform texture.
01200	
01300	In some cases we are interested in representing gross characteristics
01400	of shape, texture and other features, eg for description of trees. In
01500	other cases, we are interested  in  more  complex  descriptions  than
01600	characterized  polyhedra,  as  in  descriptions  of machined parts or
01700	people.
01800	
01900	It is not conceivable in  real  world  scenes  to  search  through  a
02000	complete set of known prototypes seeking interpretations.  The system
02100	must limit interpretations to those familiar in the context, and  use
02200	brief  descriptions  to  select  a  small  subset  of possible object
02300	interpretations.
02400	
02500	The  same  information  overload   affects   segmentation   and   the
02600	interconnection of segmentation with interpretation.  The overload is
02700	not to be solved by  merely  building  faster  computers  and  bigger
02800	memories;  hardware  improvements will aid adequate techniques but do
02900	little for exhaustive techniques.
03000	
03100	Description of simple polyhedral scenes was  difficult  enough;  with
03200	these  added  obstacles,  is there hope for success in perceiving the
03300	real world? The full problem is broader, in some places  deeper,  but
03400	in  many places shallower.  For blocks, we restricted our programs to
03500	black and white images and distinguished structures of blocks  solely
03600	on  the  basis  of  shape.  In the real world, we use color, texture,
03700	depth, size (which is not very  relevant  for  blocks),  and  surface
03800	orientation.   Our  goal  is  not  complete descriptions; for a given
03900	task, the system need be concerned with only a few objects  necessary
04000	for  its  goals.   Shapes  of  complex  objects,  while  they  may be
04100	difficult to describe, often  discriminate  very  simply  from  other
04200	objects  of  interest.   Real world objects are found in well-defined
04300	contexts; eg telephones are attached to cords. Depth  information  is
04400	particularly powerful.
     

00100			REAL WORLD VISION
00200	
00300	Studies for agricultural and earth resources surveys have  considered
00400	texture as a two-dimensional problem.  Bajcsy [] has analyzed outdoor
00500	scenes for which perspective and  three-dimensional  description  are
00600	important.      Textures  were  described  by  structures  of texture
00700	elements with spatial relations.  Descriptors  for  texture  elements
00800	and   relations   were   obtained  from  the  Fourier  transform  for
00900	directionality (if any),  size,  contrast,  and  spacing  of  texture
01000	elements.    The  Fourier  transform  was  found troublesome,however.
01100	Color and texture regions were obtained.  Some depth relations  could
01200	be  observed  from  texture gradient.   An attempt was made to obtain
01300	consistent interpretations by first confirming region  boundaries  by
01400	independent properties, making three-dimensional interpretations, and
01500	matching region descriptors with those of sky, trees, grass, etc.  in
01600	a world model.
01700	
01800	The  quality  of  interpretation  was  limited  by  unreliability  of
01900	region-growing processes. Further work in outdoor scenes attempts  to
02000	incorporate  the  world  model  and  interpretation  into  the region
02100	growing process. Regions are merged not only because of similarity of
02200	properties, but because the consistency of semantic interpretation is
02300	improved.
     

00100		Representation
00200	
00300	
00400	We  do  not  think  a  single representation is adequate throughout a
00500	system,  but  we  have  attempted  to  analyze  tasks  in  terms   of
00600	computational primitives required for descriptions of shape which are
00700	adequate for typical robot  tasks  such  as  manipulation,  collision
00800	avoidance,  display,  and  recognition.  Although many would disagree
00900	with our criteria, the design criteria were:[]
01000	a) Representations should be symbolic at a high level in order
01100	to interface with knowledge of the problem domain.
01200	b) Representations should depend on segmentation into parts,
01300	which may have subparts.
01400	c) Primitives should be three-dimensional volume descriptions,
01500		rather than surface descriptions.
01600	d) Descriptions should be generative.  A modest collection of
01700	primitives should allow description of a vast set of objects.
01800	
01900	Figures  show  experimental  results  of  computer descrition of some
02000	objects [Agin].  They give some indication of the primitives  of  the
02100	representations, and their power, even with preliminary programs. The
02200	representations [Binford 1971] depend upon segmentation  to  describe
02300	complex   objects   in  terms  of  parts.   The  representations  are
02400	grqph-structured.  Parts  are  structures  of  the  same  form.   The
02500	description of a man is shown below.
02600			       [HEAD]
02700				 |
02800				NECK
02900				 |
03000		      [ARM]--<SHOULDERS>--[ARM]
03100				 |
03200			       TRUNK
03300				 |
03400			      <HIPS>
03500			      |    |
03600			  [LEG]    [LEG]
03700	The utility of these  representations  lies  in  defining  primitives
03800	which  allow  a  natural  choice  of  parts.   Parts  are  joined  by
03900	"pasting"; holes are made by "cutting".
04000	
04100	Primitive parts are described  by  "generalized  local  translational
04200	invariance",   a   formal  construction  which  generates  solids  by
04300	transforming and translating an arbitrary cross section along a space
04400	curve  (the  axis).   If the transformation scales the cross section,
04500	then the solid generated is locally conical.  The  representation  is
04600	thus  specified  by  an axis which is a space curve, and an arbitrary
04700	normal cross section along the axis.   Snake-like  objects,  helices,
04800	toroids,  and  locally  helical  and  toroidal  shapes  are naturally
04900	described.
     

00100				Conclusion.
00150	
00300	Recently, several laboratories have begun to apply techniques
00400	from perception research to practical industrial tasks.
00450	Stanford University has completed assembly of a simple device.
00500	General Motors laboratories has succeeded in mounting a wheel on 
00600	an axle. Stanford Research Institute and Hitachi Ltd. have each
00700	demonstrated systems which can distinguish sheet metal parts
00800	on a moving conveyor belt and determine their orientation to enable
00900	manipulation. Template matching techniques were used to take 
01000	advantage of the two dimensional nature of these tasks. Moreover,
01100	the conveyor demonstrations relied on the contrast between shiny metalic parts 
01200	and the black belt to simplify segmentation. Many industrial processes 
01300	share similar constraints or can be readily redesigned to do so.
01400	We thus expect a proliferation of industrial applications of 
01500	computer perception in the near future.